|
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph. The distinction between sparse and dense graphs is rather vague, and depends on the context. For undirected simple graphs, the graph density is defined as: : For directed simple graphs, the graph density is defined as: : where E is the number of edges and V is the number of vertices in the graph. The maximum number of edges is ½ |''V''| (|''V''|−1), so the maximal density is 1 (for complete graphs) and the minimal density is 0 . ==Upper density== ''Upper density'' is an extension of the concept of graph density defined above from finite graphs to infinite graphs. Intuitively, an infinite graph has arbitrarily large finite subgraphs with any density less than its upper density, and does not have arbitrarily large finite subgraphs with density greater than its upper density. Formally, the upper density of a graph ''G'' is the infimum of the values α such that the finite subgraphs of ''G'' with density α have a bounded number of vertices. It can be shown using the Erdős–Stone theorem that the upper density can only be 1 or one of the superparticular ratios 0, 1/2, 2/3, 3/4, 4/5, ... ''n''/(''n'' + 1), ... (see, e.g., Diestel, p. 189). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Dense graph」の詳細全文を読む スポンサード リンク
|